﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode
{
    class P0043 : IProblem
    {
        public void Run()
        {
            var s = new Solution();

            var list = new List<(string, string)>(){
                ("12","1"),
                ("123","123"),
                ("33","2"),
                ("9999999","2"),
                ("166687","8"),
                ("166687","0"),
                ("8","0"),
                ("988","208"),
            };

            foreach (var tuple in list)
            {
                var num1 = tuple.Item1;
                var num2 = tuple.Item2;
                var result = s.Multiply(num1, num2);
                Console.WriteLine("num1:{0} num2:{1} result:{2}", num1, num2, result);
            }
        }



        public class Solution
        {
            public string Multiply(string num1, string num2)
            {
                //所有list都是逆序的, 即list[0]代表个位 list[1]代表十位...

                var list1 = new List<char>(num1.ToCharArray());
                var list2 = new List<char>(num2.ToCharArray());
                list1.Reverse();
                list2.Reverse();

                if (list1.Count < list2.Count)
                {
                    var t = list1;
                    list1 = list2;
                    list2 = t;
                }

                List<char> r = null;
                for (int i = 0; i < list2.Count; i++)
                {
                    var line = Multiply(list1, list2[i]);
                    for (int j = 0; j < i; j++)
                    {
                        line.Insert(0, '0');
                    }
                    if (r == null)
                    {
                        r = line;
                    }
                    else
                    {
                        r = Add(r, line);
                    }
                }

                r.Reverse();
                return new string(r.ToArray());
            }

            public List<char> Multiply(List<char> num1, char num2)
            {
                int num = num2 - '0';
                if (num == 0)
                    return new List<char>() { '0' };
                List<char> r = new List<char>(num1);
                for (int i = 1; i < num; i++)
                {
                    r = Add(r, num1);
                }

                return r;
            }

            public string Add(string num1, string num2)
            {
                var list1 = new List<char>(num1.ToCharArray());
                var list2 = new List<char>(num2.ToCharArray());
                list1.Reverse();
                list2.Reverse();

                var r = Add(list1, list2);
                r.Reverse();
                return new string(r.ToArray());
            }

            public List<char> Add(List<char> num1, List<char> num2)
            {
                if (num1.Count < num2.Count)
                {
                    var t = num1;
                    num1 = num2;
                    num2 = t;
                }
                int jinwei = 0;
                for (int i = 0; i < num2.Count; i++)
                {
                    var r = num1[i] + num2[i] - ((int)'0' << 1) + jinwei;
                    num1[i] = (char)(r % 10 + (int)'0');
                    jinwei = r / 10;
                }

                int index = num2.Count;
                while (jinwei != 0)
                {
                    if (index >= num1.Count)
                    {
                        num1.Add('0');
                    }
                    var r = num1[index] - '0' + jinwei;
                    num1[index] = (char)(r % 10 + '0');
                    jinwei = r / 10;
                    index++;
                }

                return num1;
            }
        }
    }
}
